\documentclass[11pt,a4paper,final,notitlepage]{article}
%\usepackage[latin1]{inputenc}
\usepackage{times}

\setlength{\hoffset}{0pt}  	
\setlength{\oddsidemargin}{0pt} 	% Marge gauche sur pages impaires
\setlength{\evensidemargin}{0pt} 	% Marge gauche sur pages paires
\setlength{\marginparwidth}{35pt} 	% Largeur de note dans la marge
\setlength{\textwidth}{450pt} 	% Largeur de la zone de texte (17cm)
\setlength{\marginparsep}{0pt} 	% Sparation de la marge
\setlength{\voffset}{0pt} 	% Bon pour DOS
\setlength{\topmargin}{0pt} 	% Pas de marge en haut
\setlength{\headheight}{0pt} 	% Haut de page
\setlength{\headsep}{0pt} 	% Entre le haut de page et le texte
\setlength{\footskip}{10pt} 	% Bas de page + sparation
\setlength{\textheight}{700pt} 	% Hauteur de la zone de texte (25cm) 
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{makeidx}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{tikz}

\title{Advanced Algorithms - Homework Set 2}
\author{Valentina Sintsova \{valentina.sintsova@epfl.ch\} \\ 
        Javier Picorel \{javier.picorel@epfl.ch\} \\
        Vasileios Trigonakis \{vasileios.trigonakis@epfl.ch\} \\}

\begin{document}

\maketitle

\thispagestyle{empty}
\pagestyle{empty}

\paragraph*{Question 3.}
Prove that the greedy algorithm for the minimum vertex cover problem that is based on vertex
degree has an approximation ratio of $\Theta(logn)$. Hint: for the worst-case example, build a
bipartite graph with $n$ vertices on one side, and, on the other side $n−1$ classes of vertices, one for each degree from 2 to $n$, and each class contains a number of vertices that depends on its index. The graph you build will be very large.\\\\
We will describe the process and the intuition behind generating the worst-case example for greedy with an example consisting of $n = 8$ initial vertices. We want these initial vertices to be the ones that the optimal algorithm would select and we will add more nodes in the graph so that we ``trick'' greedy to select them (the new ones). In order to be sure that greedy will select every extra node we add, we will add the vertices in the sequence that will be selected by greedy. We also do not add any edges among the newly added vertices, else the optimal algorithm would also have to cover them. Add:
\begin{itemize}
\item A vertex with degree $n = 8$ (connected to all the pre-existing vertices).
\item A vertex with degree $n-1 = 7$ (connected to all the pre-existing vertices, except the first one).
\item A vertex with degree $n-2 = 6$ (connected to all the pre-existing vertices, except the first two).
\item A vertex with degree $n-3 = 5$ (connected to all the pre-existing vertices, except the first three).
\item 2 vertices with degree $n-4 = 4$. We added 2 vertices since we have enough initial vertices for both the new ones to have a degree of 4 (and thus be selected after the ones with the degree 8,7,6,5).
\item 2 vertices with degree $n-5 = 3$.
\item 4 vertices with degree $n-6 = 2$.
\end{itemize}

\begin{center}
\begin{figure}[hbtp]
\includegraphics[width=1\linewidth]{q3.png}
\caption{Worst-case graph for greedy. The dark gray vertices are the ones selected by the optimal, while the others by greedy.}
\label{fig:greedy}
\end{figure}
\end{center}

The resulting graph looks like the one in Figure~\ref{fig:greedy}. The numbers inside each vertex are their degrees. One can notice that the three leftmost vertices are not as full as possible. Actually, they do. Assume that we add one more vertex that will make the degree of the vertex with degree 6, 7. We can do this only by adding a vertex with degree 2 or 3 (we do not have more ``space''). After the vertices with degree 8,7,6,5 has been selected by greedy, this node will have degree 4 (instead of 3 that it has), which means that it could be possibly selected by greedy, ruining our approach.

In terms of number of elements for the vertex cover we have the following:\\\\
\begin{tabular}{|l || l|}
OPT & $n = 8$\\\hline
Greddy & $\frac{n}{n} + \lfloor\frac{n}{n-1}\rfloor + \lfloor\frac{n}{n-2}\rfloor+ \lfloor\frac{n}{n-3}\rfloor+ \lfloor\frac{n}{n-4}\rfloor+ \lfloor\frac{n}{n-5}\rfloor+ \lfloor\frac{n}{n-6}\rfloor$\\
\end{tabular}

Now, in the general case of $n$ initial vertices\footnote{$n$ are the ones selected by the optimal solution}, greedy will select:
\[N_{Greedy} = \frac{n}{n} + \lfloor\frac{n}{n-1}\rfloor + \lfloor\frac{n}{n-2}\rfloor+ \lfloor\frac{n}{n-3}\rfloor+ \ldots + \lfloor\frac{n}{n-(n+3)}\rfloor + \lfloor\frac{n}{n-(n+2)}\rfloor = \]
\[n(\frac{1}{n} + \lfloor\frac{1}{n-1}\rfloor + \lfloor\frac{1}{n-2}\rfloor+ \lfloor\frac{1}{n-3}\rfloor+ \ldots + \lfloor\frac{1}{3}\rfloor + \lfloor\frac{1}{2}\rfloor)\]
For big $n$ and approximating without the floors:
\[N_{Greedy} \simeq n\sum_{i = 2}^{i = n} \frac{1}{i} \stackrel{n \rightarrow \infty}{\simeq} n(ln(n) - 1)\]
So, greedy will select $\Theta(nlogn)$ vertices, while the optimal will select $n$, hence the approximation ratio for greedy is $\Theta(logn)$.




\paragraph*{Question 4.}
You are faced with the following optimization problem. Your company manufactures two component resins; both the resin and its constituent components are made in batches. Each batch of resin is made by combining a batch of component of type A with a batch of component of type B. You take delivery of many batches of each of A and B at once; they come from
various producers and so are somewhat uneven consistency. However, your process requires
that the two have closely matched consistencies, so you measure the consistency of each batch
on delivery, call it $c$ (an integer-valued function). You can combine a batch $a_i$ of constituent A and a batch $b_i$ of constituent B if and only if their consistencies obey $|c(a_i)-c(b_i)| \leq T$, for a fixed threshold $T$.\\\\
Assume that you have in stock $n$ batches of constituent A and $m$ batches of constituent B, with
$m = \Theta(n)$; show that you can maximize the number of batches of resin that you can produce
from this stock using an algorithm that runs in $o(mn)$ time.\\\\
The algorithm we will use for the matching is similar to the merge step of mergesort. Our algorithm takes the following steps:
\begin{enumerate}
\item sort A (costs $O(nlogn)$)
\item sort B (costs $O(mlogm)$)
\item perform the matching on the sorted A and B starting from the first elements ($i,j = 1$) as following:
\begin{itemize}
\item if $|a_i - b_j| \leq T$, then match them and increase $i, j$ by one
\item else, if $a_i > b_j$, increase $j$ by one, else increase $i$ by one
\item repeat this process until all As or Bs has been processed
\end{itemize}
\end{enumerate}
This part of the algorithm costs (in terms of steps) $O(n + m)) = O(2n) = O(2m)$, since $n = \Theta(m)$.

We claim that the aforementioned algorithm produces a maximum matching. This follows the intuition that if the current smallest elements can match, we should match them since even if both of them can be matched with larger elements, we will not get a bigger matching. If we could do so, then the following situation should be possible\footnote{from now on when we write $a_i$ we mean the cost of $a_i$ which is $c(a_i)$}:

\ifx\du\undefined
  \newlength{\du}
\fi
\setlength{\du}{15\unitlength}
\begin{center}
\begin{tikzpicture}
\pgftransformxscale{1.000000}
\pgftransformyscale{-1.000000}
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetstrokecolor{dialinecolor}
\definecolor{dialinecolor}{rgb}{1.000000, 1.000000, 1.000000}
\pgfsetfillcolor{dialinecolor}
% setfont left to latex
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetstrokecolor{dialinecolor}
\node[anchor=west] at (10.000000\du,3.000000\du){a1};
% setfont left to latex
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetstrokecolor{dialinecolor}
\node[anchor=west] at (10.000000\du,3.800000\du){};
% setfont left to latex
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetstrokecolor{dialinecolor}
\node[anchor=west] at (10.000000\du,4.600000\du){a2};
% setfont left to latex
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetstrokecolor{dialinecolor}
\node[anchor=west] at (15.000000\du,3.000000\du){b1};
% setfont left to latex
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetstrokecolor{dialinecolor}
\node[anchor=west] at (15.000000\du,3.800000\du){};
% setfont left to latex
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetstrokecolor{dialinecolor}
\node[anchor=west] at (15.000000\du,4.600000\du){b2};
\pgfsetlinewidth{0.100000\du}
\pgfsetdash{}{0pt}
\pgfsetdash{}{0pt}
\pgfsetbuttcap
{
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetfillcolor{dialinecolor}
% was here!!!
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetstrokecolor{dialinecolor}
\draw (11.000000\du,3.000000\du)--(15.000000\du,4.000000\du);
}
\pgfsetlinewidth{0.100000\du}
\pgfsetdash{}{0pt}
\pgfsetdash{}{0pt}
\pgfsetbuttcap
{
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetfillcolor{dialinecolor}
% was here!!!
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetstrokecolor{dialinecolor}
\draw (11.000000\du,4.000000\du)--(15.000000\du,3.000000\du);
}
\pgfsetlinewidth{0.100000\du}
\pgfsetdash{}{0pt}
\pgfsetdash{}{0pt}
\pgfsetbuttcap
{
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetfillcolor{dialinecolor}
% was here!!!
\definecolor{dialinecolor}{rgb}{0.000000, 0.000000, 0.000000}
\pgfsetstrokecolor{dialinecolor}
\draw (11.000000\du,3.000000\du)--(15.000000\du,3.000000\du);
}
\end{tikzpicture}
\end{center}
$a_1$ matched with $b_{1,2}$ and $a_2$ matches with $b_1$, but $a_2$ does not match with $b_2$. If this case is possible, then our matching algorithm would not be optimal, since we would be able to take a bigger match than the one it produces.
Expressing the following problem with types gives:
\[|a_1 - b_1| \leq T\]
\[|a_1 - b_2| \leq T\]
\[|a_2 - b_1| \leq T\]
\[a_1 \leq a_2 \Rightarrow a_2 = a_1 + c_a, c_a \geq 0\]
\[b_1 \leq b_2 \Rightarrow b_2 = b_1 + c_b, c_b \geq 0\]
and if the problem exists it should be that $|a_2 - b_2| > T$. Without a loss of generality, assume that $b_2 < a_2 \Rightarrow a_2 = b_2 + t$, with $t > T$. Then:
\[|a_2 - b_1| \leq T \Rightarrow |b_2 + t - b_1| \leq T \stackrel{c_b = b_2 - b_1}{\Rightarrow}
|c_b + t| \leq T\]
but $t > T$ and $c_b > 0$, thus impossible.

So, we proved that our algorithm will produce the largest possible matching.

Assuming $n > m$, the complexity of our algorithm is $O(nlogn)$. We know that $m=\Theta(n)\Leftrightarrow n =\Theta(m)$, therefore $logn = o(m)$ and thus $O(nlogn) = O(nm)$.




















\end{document}
